VARGA→0
HARRISON→0
Hamlet→v
Berlekamp,→vi
Brillhart,→vi
Collins,→vi
Cook,→vi
Lehmer,→vi
MacLaren,→vi
Muller,→vi
Stolarsky,→vi
Zassenhaus,→vi
Knuth→vif
TEX→vii
Aspvall,→vii
Brent,→vii
Dieter,→vii
Fischer,→vii
Gosper,→vii
Hoaglin,→vii
Kahan,→vii
Liang,→vii
Reiser,→vii
Waterman,→vii
Winograd,→vii
Wunderlich→vii
Howe→vii
COLTON→vii
exercises, notes on→ixf
Bellman→ix
RECORDE→xi
VON NEUMANN→1
GAY→1
OWEN→1
Simulation→1
random numbers→1f
Sampling→1
choice,random→2
dice→2
independent sequence of random numbers→2
distribution→2
uniform→2
flat distribution, see uniform distribution→2
distribution, uniform→2
Tippett→2
random numbers, machines for generating→2f
Kendall→2f
Babington-Smith→2f
RAND Corporation→2f
ERNIE→3f
Thomson→3
von Neumann→3f
``middle-square'' method→3f
pseudo-random→3
quasi-random→3
Forsythe→4
Metropolis→4
cycles→4f
Knuth→4
middle-square method→7f
Analysis of algorithms→7f
Floyd→7
Brent→7
generating→9f
uniform distribution→9f
linear congruential→9f
Lehmer→9f
modulus→9f
multiplier→9f
increment→9f
period→9
Thomson→10
Rotenberg→10
multiplicative congruential→10
mixed congruential→10
modulus→11f
word size→11
$e$→11
addition modulo $w$→11f
multiplication modulo $w$→11f
overflow→11
prime factors→12f
factorization→12f
DEC 20→14
IBM System/370 computers→14f
System/370→14f
WM1→15
multiplier→15
Greenberger→16
Hull→16
Dobell→16
multiplicative congruential→18
Euler's theorem→19
order of $a$ modulo $m$→19f
primitive element→19f
Carmichael→19
cycle→21
Thomson→21
Marsaglia→22
potency→22f
Coveyou→26
von Neumann→26
middle-square→26
accuracy→26
Fibonacci sequence→26
Green,→26
Smith,→26
Klem→26
Mitchell→26
Moore→26
Brent→27
Zierler→28
Brillhart,→28
Reiser→28
Fibonacci sequence→28
primitive polynomial modulo $p$→28f
Alanen→29
Knuth→29
exclusive or→30
Tausworthe,→30
Watson,→30
Mitchell→30
Moore→30
Lewis→30
Payne→30
exclusive or→30
Bright→30
Enison→30
Martin→31
combination of random number generators→31
Westlake→31
MacLaren→31
Marsaglia→31
shuffling→32f
Bays→32
Durham→32
Gebhardt→33
Fibonacci sequence→33
Coveyou→34
Fibonacci sequence→34
period length→34
cycle→34f
Martin,→35
Rees→36
Reiser→36
discrepancy→37
Waterman→37
testing random numbers→38f
Randomness, testing for, see testing→38
Matrix→38
Gardner→38
ART ON REPRO REQUIRED→38
pi→38
Huff→39
chi-square test→39f
dice→39f
chi-square distribution, table→41
Abramowitz→41
Stegun→41
degrees of freedom→41f
percentage point→43
locally nonrandom behavior→43
MacLaren→44
Marsaglia→44
Fibonacci→44
Lehmer→45
Rotenberg→45
Kolmogorov-Smirnov test→45f
distribution function→45f
empirical distribution function→47f
Kolmogorov--\hskip .1em Smirnov distribution, table→48
Locally nonrandom behavior→49f
Globally nonrandom behavior→49f
maximum of 5→49f
Fibonacci→50
chi-square test→50f
Lehmer's→52f
Fibonacci→52
ENIAC→52
Pearson→52
Cochran→53
Poisson→53
Pearson→54
incomplete gamma function→54
Kolmogorov→54
Smirnov→54
Durbin,→54
Birnbaum→55
Tingey→55
Smirnov→55
Darling→56
dice→56
maximum of 5→57
Polar coordinates→57
incomplete gamma function→58
KS test, see Kolmogorov--\hskip .1em Smirnov→58
Gonzalez→58
Sahni→58
Franta→58
Equidistribution test→59
Frequency test→59
STOPPARD,→60
Serial test→60f
Good→60
Gap test→60f
coupon-collector's test→61f
run test→61
Poker test→62f
Partition test→62f
von Schelling,→63
Permutation test→64f
permutations mapped to integers→64
mixed-radix representation→64
factorial number system→64
Run test→65f
Wolfowitz→67
maximum-of-$t$ test→68
Collision test→68f
hashing→68
Serial correlation test→70f
Dixon→71
Anderson→71
Walker,→71
fast Fourier transforms→71
Schmid,→71
Kendall→72f
Babington-Smith→72f
frequency test→72f
serial test→72f
gap test→72f
poker test→72f
Greenwood→72
run test→72f
Bienaym\'e→72
Kermack→72
McKendrick→72
Levene→72
Wolfowitz→72
Barton→72
Mallows,→72
collision test→72f
Christiansen→72
Geiringer→73
$e$→73
Quick→74
serial correlation coefficient→75
permutation test→75
Theoretical tests for randomness→75f
{\:na priori\/} tests→75
globally nonrandom behavior→75
permutation test→76f
sawtooth function→77f
serial correlation test→78f
Dedekind sum, generalized→78f
Dedekind→78
Riemann→78
Reciprocity law→79
roots of unity→79f
Carlitz.→79
exponential sums→79f
Euclid's algorithm→81
partial quotients→83
Coveyou→84
Greenberger→84
Dieter→85
Knuth,→85
Rademacher→86
Grosswald→86
sawtooth→86f
replicative law→86
Fourier series→86
reciprocity law→86
Carlitz→86
Rademacher→86
Dieter→87
Coveyou→88
Fibonacci generator→88
potency→88
spectral test→89f
Baumgart→90
Givens→90
accuracy→90
serial test→91
lattice→93
positive definite quadratic form→94
Schmidt orthogonalization process→97
Gosper→98
Dieter→98
spectral test, algorithm for→98f
exhaustive search→99
Borosh→104f
Niederreiter→104f
Dedekind sums→104
Waterman→104f
Taussky→104
Lavaux→104f
Janssens,→104f
System/370→104
\hbox {\:tRANDU}→104f
Gosper,→104
Haynes→104
Marsaglia→104
Cassels,→105
serial test→105f
Niederreiter→105
exponential sums→105f
discrepancy→105f
Niederreiter→109f
Korobov→110
Kuipers→110
Coveyou→110f
MacPherson→110
Janssens→110
Dieter→110
Marsaglia,→110
Wood,→110
Beyer,→110
Roof,→110
Williamson,→110
Zaremba→110
Hermite,→111
positive definite quadratic form→111
Waterman,→111
Gosper→112
Alekseev→112
Hlawka,→113
Niederreiter→113
Zaremba→113
Euclid's algorithm→113
Borosh→113
random numbers, generating→114f
random numbers, using→114f
random waiting time→114
exponential distribution→114
von Neumann→114
Marsaglia,→114
Ahrens,→114
Dieter→114
random integer→114
discrete distribution→115f
Walker→115
aliases→115
dice→115f
distribution function→116
inverse function→116
uniform deviate→116f
maximum-of-$t$ test→117
square root→117
normal distribution→117f
polar method→117f
Box,→117
Muller,→117
Marsaglia→117
normal deviates→117f
random point in a circle→118
polar coordinates→118
rectangle-wedge-tail→118f
Marsaglia→118
mixture of distribution functions→118f
density function→119
uniform distributions→119f
Rectangular distribution, see uniform distribution→119
wedge-shaped distributions→120f
von Neumann→120
rejection method→120f
polar method→120
squeeze method→121
Walker→122
alias→122
Marsaglia,→123
MacLaren,→123
Bray,→123
Ananthanarayanan,→123
Paul,→123
odd-even method→124f
Forsythe→124f
von Neumann→124
Ahrens→124f
Dieter,→124f
Brent→125
Kinderman→125f
Monahan→125f
Ratio method→125f
dependent random variables→127
correlation coefficient→127
exponential distribution→128f
exponential deviate→128f
arrival time→128
radioactive decay→128
Logarithm→128
Marsaglia→128
Sibuya,→128
Ahrens→128
gamma distribution→129
Ahrens→129f
Dieter,→129
Marsaglia,→129
beta distribution→129
J\"ohnk→130
Cheng,→130
chi-square distribution→130
F-distribution→130
variance-ratio distribution→130
random point on sphere→130
polar method→130f
Brown,→130
Beckenbach→130
random point in a sphere→131
Brent→131
Knop,→131
discrete distributions→131f
geometric distribution→131f
waiting time→131
gap test→131
binomial distribution→131f
Ahrens,→131
Poisson distribution→132f
exponential distribution→132
geometric→132
radioactive substance→132
Ahrens→132
Dieter→132
exponential deviates→132
sorted uniform deviates→132
binomial→133
Poisson→133
Ahrens→133
Dieter→133
Knuth→133
Yao,→133
Traub→133
Walker→134
rejection method→134f
Brent→134
covariance→134
Ahrens→135
gamma→135
distribution function→135
geometric distribution→135
generating function→135
negative binomial distribution→135
Poisson distribution→135f
von Neumann→135f
Ulam,→135
Ahrens→136
Brent→136
random point on an ellipsoid→136
Bentley→136
Saxe→136
sorted uniform deviates→136
sampling→136f
random combination→136f
Selection sampling→137f
seed, choice of→137
choice of seed→137
Fan,→137
Muller,→137
Rezucha→137
Jones,→137
Reservoir sampling→138f
Waterman→139
random permutation→139f
shuffling→139f
Moses→140
Oakford,→140
Durstenfeld,→140
Nijenhuis→140
Wilf→140
Golomb→141
Dahl→141
sampling, weighted→141
randomness, definitions of→142f
von Mises→142
Lehmer→142
Franklin→142
Probability: Frequency of occurrence→143
equidistributed→143f
Probability, over the integers→143f
$\mathop {\char P\char r}$→143
$k$-distributed sequence→144f
$∞$-distributed sequence→144f
$[\,0,1)$ sequence→144
$b$-ary sequence→144
$b$-ary number→144
pi→144f
Locally nonrandom behavior→145
Finite sequence, random→145
$k$-distributed sequence→145f
Riemann integration→146f
permutation test→147
serial correlation test→148
Niven→149
Zuckerman→149
Cassels,→151
serial test→151
maximum-of-$t$ test→151
collision test→151
gap test→151
poker test→151
run test→151
coupon collector's test→151
Franklin→152f
pi→152
Knuth→152
Korobov,→152
Lebesgue measure→154
Lebesgue integration→154
Effective algorithm→154f
pi→154
gambling system→155
subsequence rule→155f
computability→155f
Wald→157
equidistributed→157
van der Corput→157
Halton,→157
Ramshaw,→157
Lebesgue measure→159f
binomial distribution, tail→160
Finite sequences, random→161f
locally nonrandom behavior→162
$\mathop {\char P\char r}$→162
$k$-distributed→162
Kolomogorov→163
Rees→163
Martin-L\"of→163
Turing machine→164
Chaitin→164
Zvonkin→164
Levin,→164
$∞$-distributed→164
Borel→164
completely equidistributed sequence→164f
Korobov→164
Franklin,→164
Kuipers→164
Niederreiter→164
$k$-distributed→164
von Mises→165f
Copeland→165
admissible numbers→165
Bernoulli sequences→165
Wald→165
Lebesgue measurable→165
computability→165
Church→165
effective algorithm→165
Kolmogorov→165
Besicovitch→165
Howard,→165
Loveland→165f
Herzog→166
Owings,→166
Chaitin→166
Martin-L\"of→166
Popper→166
Schnorr→166
species of measure zero→166
Brouwer→166
equidistributed→166
$k$-distributed→166f
$\mathop {\char P\char r}$→166f
$∞$-distributed→167f
maximum-of-$k$ test→167
gap test→167
run test→167
coupon-collector's test→167
Franklin→167f
Mahler,→167
Weyl→168
exponential sums→168
white sequence→168
serial correlations→168
Coppersmith→168f
Loveland→169
Schmidt→169
Good→169
random numbers, generating→170f
random numbers, summary→170f
linear congruential sequence→170f
seed→170
linear congruential sequence, choice of starting value→170
linear congruential sequence, choice of modulus→170
linear congruential sequence, choice of multiplier→170f
linear congruential sequence, choice of increment→171
accuracy→171
subtractive method→171f
portable random number generator→171f
FORTRAN→171f
Fibonacci→172
floating point numbers→172f
RANDU→173
Nance→173
Overstreet→173
Sowey→173
Hammersley→173
Handscomb→173
Lovelace→173
dice→174
craps→174
playwriting→174f
robber→174f
sheriff→174f
Wolf→176
Ross→176
Morse→176
Pfeiffer→176
exclusive-or→177
cryptanalysis→177
ARITHMETIC→178f
NAPIER→178
LA TOUCHE→178
WALES→178
PARLETT→178
POSITIONAL NUMBER SYSTEMS→179f
representation of numbers→179f
Radix: base of positional notation→179
decimal digits→179
binary→179
ternary→179
quaternary→179
quinary→179
radix point→179
digits→179
leading digit→179
trailing digit→179
most significant digit→179
least significant digit→179
significant digit→179
binary digits→179
bits→179
hexadecimal digits→179
number systems, primitive→179
Roman numerals→179
sexagesimal→180
floating point→180
Babylonian mathematics→180
Neugebauer,→180
van der Waerden→180
Dresden→180
Knuth,→180
Maya Indians→180
vigesimal number system→180
Thompson,→180
Greek mathematics→180f
abacus→180
decimal notation→181f
Indian mathematics→181
Hindu science→181f
Arabic mathematics→181f
Persian mathematics→181f
al-Khw\A arizm\A \i →181
Leonardo Pisano→181
Fibonacci→181
Smith→181
Ptolemy→181
sexagesimal→181
decimal fractions→181f
Chinese mathematicians→181f
Tsu Chhung-Chih→181
Pi→181
weights and measures→182f
al-Uql\A \i dis\A \i →182
Saidan→182
al-Kash\A \i →182
van Ceulen→182
Rudolff→182
Vi\`ete→182
Stevin→182
Smith,→182
Boyer,→182
binary→182f
Seidenberg→182
number systems, primitive→182
sexagesimal→182
Wallis,→182
Pascal→183
decimal system→183
duodecimal→183
Weigel→183
Jordaine,→183
mixed-radix number systems→183
liquid measure→183
Harriot→183
Raleigh→183
Shirley,→183
Caramuel Lobkowitz→183
ternary→183
quaternary→183
quinary→183
Septenary (radix 7) number system→183
octal number system→183
Nonary (radix 7) number system→183
duodecimal→183
sexagesimal→183
Leibniz→184f
Zacher,→184
Napier→184
local arithmetic→184
abacus→184
Gardner→184
Bernoulli→184
Pi→184
radix conversion→184
Gehrhardt→184
Charles XII→184
octal number system→184f
Voltaire→184
Swedenborg,→184
Jones,→184
Phalen,→184
Nystrom→184f
hexadecimal→185f
Taylor→185
Colenne,→185
Mariage,→185
Archibald→185
Peano→185
Bowden→185
Glaser→185
Babbage→185
Analytical Engine→185
Wilkes,→185
Phillips→185
Wales→186
Wynn-Williams→186
Atanasoff→186
Stibitz→186
Couffignal→186
Valtat→186
Schreyer→186
Zuse→186
Stibitz→186
binary-coded-decimal→186
Randell→186
Burks,→186
Goldstine,→186
von Neumann→186
Buchholz→186
{\:tMIX}→186
multiple-precision arithmetic→186
negative numbers, representation of→186f
signed-magnitude representation→186f
minus zero→186
ten's complement notation→186
complement notation→187
nines' complement notation→187
two's complement→187
ones' complement→187
{\:tMIX}→187
radix point→187
radix conversion→188
negative radix→188f
negadecimal→188
Gr\"unwald→188
radix conversion→188
Kempner→188
Pawlak→188
Wakulicz→188
Wadel→188
Knuth→189
quater-imaginary→189
complex radices→189f
Knuth→189
radix conversion→189
Gr\"unwald→189
Penney→189
Farmwald→190
twindragon→190
Gosper→190
Maas→190
balanced ternary number system→190f
trits→190
radix conversion→191
Addition→191
Subtraction→191
multiplication→191
Bachet→192
Fibonacci→192
Ahrens,→192
Bharati→192
Indian mathematics→192
Colson→192
Leslie→192
Cauchy→192
Lalanne→192
Engineering Research Associates→192
SETUN→192
mixed-radix number system→192f
factorial number system→192
weights and measures→193f
Cantor→193
Parry,→193
binomial number system→193
Fibonacci number system→193
phi number system→193
Gray code→193
roman numerals→193
binary→193f
signed magnitude→193f
negabinary→193f
balanced ternary→193f
quater-imaginary→193f
radix, complex→193f
{\:TMIX}→193
radix point→193
nines' complement→194f
ten's complement→194f
complement notations→194f
octal→194
hexadecimal→194
mixed-radix notation→194f
radix conversion→194
decimal system→194f
negadecimal→194
Matula→194f
Shannon→195
balanced decimal→195
Cook→195
rational number, positional representation of→195
Mendelsohn→195
reversing binary representa\-tion→196
revolving binary representation→196
de Bruijn→196f
binary basis→196
2-adic numbers→197
$p$-adic numbers→197
field→197
square root→197
Ruzsa→197
ternary→197
quinary→197
Klarner→197
Floating point arithmetic→198f
Avogadro's→198
Planck's→198
excess in floating point exponents→198
floating binary→198
floating decimal→198
Exponent part of floating point number→198f
Fraction part of floating point number→198f
characteristic→199
mantissa→199
{\:tMIX}\ floating point attachment→199
normalized→199f
Floating point addition→200f
floating point subtraction→200f
fraction overflow→201
rounding→201
rounding overflow→201
exponent overflow→201
exponent underflow→201
\hbox {\:tACC}: Floating point accumulator→202f
\hbox {\:tOFLO}→202
JXO→203
Floating point multiplication→204f
Floating point division→204f
rounding overflow→204
fix-to-float→205
Conversion of representations→205
debugging→205f
exponent underflow→206f
exponent overflow→206
programming languages→206
gradual underflow→206
Electrologica X8→206
relative error→206
accuracy→206
rounding→206
Kahan→206
Palmer→206
rounding overflow→207
Rounding→207
{\:tMIX}→208f
floating point attachment→208
\hbox {\:tFADD},→208f
\hbox {\:tFSUB},→208f
\hbox {\:tFMUL},→208f
\hbox {\:tFDIV},→208f
\hbox {\:tFLOT},→208f
\hbox {\:tFCMP}→208f
\hbox {\:tFIX}→208f
rounding overflow→208
sexagesimal→209
Babylonian mathematicians→209
Neugebauer→209
Apollonius→209
Pappus,→209
Oughtred→209
slide rule→209
Torres→209
Zuse→209
Stibitz→209
Infinity, representation of→209
Model V→209
Mark II→209
Randell,→209
floating binary arithmetic→210f
von Neumann→210
EDVAC→210
interpretive systems→210
Wheeler→210
Wilkes,→210
Gill→210
floating decimal→210
Stark→210
MacMillan→210
McCracken,→210
Carr→210
Wadey,→210
Knuth,→210
Kesner,→210
Brooks→210
Iverson,→210
Campbell,→210
Buchholz→210
Coonen→210
Kahan→210
Stone→210
Planck's→211
Zuse,→211
floating point addition→211f
\hbox {\:TFADD}→211
balanced ternary notation→211
Kahan→211
rounding overflow→211
interval arithmetic→212
conversion of representations→212
float-to-fix conversion→212
floating point mod→212
Smith→212
hardware, algorithms suitable for (exercise 15)→212
Cocke→212
two's complement→212
floating point numbers, two's complement→212
normalizing→212
JOHNSON→213
JEFFERSON→213
Accuracy of Floating Point Arithmetic→213f
significant figures→213
relative error→213
La Touche→214
exponent underflow→216
exponent overflow→216
Cauchy's ineqality (is on this page)→216
standard deviation→216
mean→216
Welford,→216
relative error→216f
floating point comparison→218f
Neighborhood of a floating point number→218
floating point addition→219f
floating point subtraction→219f
tail of a floating point number→220
rounding→221f
drift→222
round to even→222
round to odd→222
truncation→222
Unnormalized floating point arithmetic→223f
normalizing→223
Avogadro's→223
Planck's→223
Ashenhurst→225f
Metropolis→225f
Rall→225
Interval arithmetic→225f
range arithmetic→225
Avogadro's→225
Planck's→225
overflow→226
underflow→226
Tannery→226
round to even→226
Scarborough→226
Bauer→226f
Samelson,→226f
Carr→226f
Fischer,→226
Wilkinson,→226
Kahan,→226
Brent,→226
van Wijngaarden→227
M\o ller→227
Dekker→227
Linnainmaa→227
Kahan→227
Reiser→227
Knuth,→227
MANIAC III→227
Gray→227
Harrison,→227
Wadey,→227
Gibb,→227
Chartres,→227
Moore→227
floating point multiplication→227f
exponent overflow→227
floating point reciprocal→228f
floating point division→228f
floating point comparison→228f
Kahan→228
floating point mod→228
unnormalized→229f
Bj\"ork→229
standard deviation→229
floating point summation→229
\hbox {\:TFCMP}→229
hardware, algorithms suitable for (exercise 17)→229
Kahan→229
Linnainmaa→229
Dekker→229
drift→229f
intervals→230
minus zero→230
infinity, representation of→230
floating point subtraction→230
cancellation error→230
Diamond→230
Kahan→230
Double-Precision Calculations→230f
fraction parts→231
exponent part→231
cosine→231
floating point trigonometric subroutines→231
double-precision addition→232f
double-precision subtraction→232f
carries→232f
signed-magnitude→232
Normalization→233
minus zero→234
double-precision multiplication→234f
Double-precision floating division→235f
double-precision addition→235
WM1→236
triple-precision floating point→237
Ikebe,→237
overflow→237
conversion of representations→237
accuracy→237
Dekker→237
quadruple-precision→237
Distribution of Floating Point Numbers→238f
floating point addition→238f
floating point subtraction→238f
Sweeney→238
normalization→239
floating decimal→239
Newcomb→239
Benford,→240
leading-digit law→240f
logarithmic law of leading digits→240f
slide rule→240
Hamming→240
Raimi,→242
probability→242f
Pr→242
Franel,→243
Riemann-integrable→244
generating functions→246f
Flehinger→247
Raimi,→247
Konheim,→247
floating binary→248
floating hexadecimal→248
Diaconis→248
Hamming→248
floating point multiplication→248f
fraction overflow→249
Diaconis→249
Duncan→249
Pr→249
harmonic probability→249
Multiple-precision arithmetic→250f
addition→250f
subtraction→250
multiplication→250f
division→250f
quotient→250
remainder→250
places→250
conversion of representations→250
carry→251f
induction on the computation→251
borrow→252
\hbox {\:tWM1}→253
multiplication,→253f
carry→254f
induction→254
division,→255f
borrow→258
carry→258
complement notation→261f
two's complement→261f
ones' complement→261f
analysis of algorithms→262f
carries→262f
generating functions→262f
Lehmer→263
Ballantine,→263
von Neumann→263
Goldstine→263
Pope→263
Stein→263
Cox→263
Luther,→263
Stein,→263
Krishnamurthy→264
Nandi→264
Collins→264
Musser→264
Fourier division→264
Fourier,→264
Lehmer,→264
Uspensky,→264
Newton's method→264
reciprocal→264
Rabinowitz→264
Krishnamurthy→264
Laughlin,→264
ones' complement→264
Stroud→265
Secrest,→265
Blum,→265
Tienari→265
Suokonautio,→265
Collins,→265
Brent,→265
hardware→265f
Reitwiesner,→265
MacSorley→265
Metze,→265
Garner,→265
Winograd,→265
Brent→265
Floyd,→265
Sun Ts\u u→265
al-Khw\A arizm\A \i →265
al-Uql\A \i dis\A \i →265
Fibonacci→265
Recorde→265
proof→265f
inductive assertions→265f
Hindu→265
Arabic→265
al-Uql\A \i dis\A \i →265
linked memory→266
linear lists→266
carry→266
mixed-radix→266
addition, mixed-radix→266
borrow→266
subtraction→266
multiplication of fractions→266
division→266f
Svoboda,→267
balanced ternary→268
division, balanced ternary→268
quater-imaginary number system→268
division, quater-imaginary→268
Nadler,→268
Pawlak→268
Wakulicz,→268
square roots→268
linked memory→268
decuple-precision→268
floating point→268
pi→268
Shanks→268
Wrench,→268
Guilloud→268
Bouyer→268
Salamin→268
Modular Arithmetic→268f
Chinese remainder theorem→269f
parallel computers→270
real-time→270
Euler's theorem→270
Sun→271
Needham→271
Chhin→271
Dickson→271
addition, mod m→271
subtraction, mod m→271
ones' complement→272
conversion of representations→273
casting out nines→273
proofs, constructive versus nonconstructive→273
Euler's totient function $\varphi (n)$→273
Garner→274
Fraenkel,→274
Szab\'o→275
Takahasi→275
Ishibashi,→275
linear equations→276
Borosh→276
Fraenkel→276
CDC 1604→276
McClellan,→276
Bareiss,→276
Svoboda→276
Valach→276
Garner→276
Fraenkel→276
Sch\"onhage→276
Szab\'o→276
Tanaka→276
Chinese remainder theorem, generalized→276
Automorphic numbers→278
multiplication→278f
recursive process→279f
Karatsuba→279
calculating prodigies→279
mental arithmetic→279
Toom→280
Cook→280
interpolation→281
factorial powers→281
Stirling number→282
Toom→282
Cook→282
recursive→283f
Toom→284
Cook→284
modular→287f
Sch\"onhage→287f
Chinese remainder theorem→288f
Euclid's algorithm→289
convolution→290f
Fourier transform→290f
Toom→290
Strassen→290f
FFT, see Fast Fourier Transform→290
fast Fourier transform→290f
inverse Fourier transform→291
fixed point arithmetic→292f
error estimates→293
absolute error→293
truncate→293
pointer machine→295
storage modification machines→295
linking automata→295
division→295f
Newton's method→295
reciprocal→295
Cook→296
Anderson→296
Earle,→296
Goldschmidt,→296
Powers,→296
Brent→297
linear iterative array→297f
automata→297f
hardware, suitable algorithms for→297f
integrated circuit module→297
Atrubin,→299
Winograd→299
Wallace,→299
Yao→299
Baker→300
fast Fourier transform→300
convolution→300
Sch\"onhage→300f
Strassen→300
pointer machine→301
Cook→301
Fischer→301
Stockmeyer→301
Paterson→301
Fischer,→301
Meyer→301
pointer machines→301
radix conversion→302f
conversion of representations→302f
Samet,→304
remainder→305
hardware;→305
AND→305
DOUBLING→305
BINARY-CODED DECIMAL→305
octal→306f
Soden,→306
casting out nines→307
binary search→307
Rozier,→308
Floating point conversion→309f
Multiple-precision conversion→309f
Oughtred→309
al-Kash\A \i →309
Jones→309
Legendre→309
Goldstine→310
von Neumann→310
Koons→310
Lubkin→310
Bauer→310
Samelson→310
Lake→310
hardware→310
Stroud→310
Secrest→310
Kanner→310
Metropolis→310
Ashenhurst→310
Sikdar→310
weights and measures→310
mixed-radix conversion→310
Taranto→310
negabinary→311
halving→311
bit manipulation→311
hardware→311
binary-coded decimal→311
multiple-precision conversion→311
Sch\"onhage→311
floating point conversion→311
Matula→312
binary-coded decimal number→312
bit manipulation→312
hardware→312
rational arithmetic→313f
fractions→313f
Multiplication of fractions→313
Division→313
Addition→313
subtraction→313
fixed slash→314
floating slash→314
floating point→314
slash arithmetic→314f
round→314
mediant rounding→314
Henrici,→315
Matula,→315f
Zaremba→315
Kornerup→315f
comparing two fractions→315
representations for $∞$→315
overflow→315
greatest common divisor→316f
gcd: Greatest common divisor→316
least common multiple→316f
lcm: Least common multiple→316
Euclid's algorithm→317f
Eudoxus→318
von Fritz→318
Egyptian→318
Babylonian→318
algorithms→318
Knuth,→318
Euclid→318f
Greek math→318f
proof→319
induction→319f
Stein→321
halving→321
binary gcd algorithm→321f
MIX, binary version→322f
SLB→322
SRB→322
JAE→322
JAO→322
JXE→322
JXO→322
Halve→322
Euclid's algorithm→323f
Harris→323
Extended Euclid's algorithm→325f
Bradley→325
linear equations→326
Diophantine equations→326f
multiple-precision gcd→327f
Lehmer→328
binary gcd algorithm→330f
lattice-point model→331f
recurrence equations→332f
Brent→335
Traub→335
least common multiple→336
balanced ternary→336
binary gcd algorithm→336f
inclusion and exclusion→337
M\"obius function→337
Ces\`aro→337
divide $u$ by $v$ modulo $m$→337
reciprocal modulo $m$→337
lattice-point model→338f
Brent→338f
determinant→338
Harris→339
Gosper→339
Pratt→339
continued fractions→339f
Perron,→339
Khinchin,→339
Wynn→339
Wall,→339
Tropfke,→339
Euler→340
continuants→340f
regular continued fraction→341f
infinite continued fraction→341
partial quotients→342
Greek math→342
Eudoxus→342
Becker,→342
Fibonacci numbers→343
Lam\'e→343
Floyd→344
lattice-point model→344
Gauss,→346
Laplace→346
Kuz'min→346
L\'evy→346
Wirsing→347f
linear operators→347f
Knopp,→347
Wirsing→350
Babenko→350f
MIX (actually 1009!)→350
\t Iur'ev→350
measure theory→350f
partial quotients→351f
regular continued fraction→352
von Mangoldt's function→355
Dixon→356
Heilbronn→356f
Porter→356
Knuth→357
Collins,→357
determinant→358
regular continued fraction→358f
continuant→358f
Lagrange→359f
decimal system→359
quadratic irrationality→359
Davenport,→359
LeVeque,→359
periodic→359
Hurwitz,→360
doubling a continued fraction→360
halving a continued fraction→360
Gosper→360
coroutine→360
Euler,→360
tangent→360
Euler's constant→360
Sweeney→360
Wrench,→360
Shanks,→360
Wirsing→361
Babenko→361
von Mangoldt function→361
M\"obius function→361
Euler totient function→361
least remainder algorithm→361
Morse code→361
Euler,→361
Heilbronn→362
Yao→362
Knuth→362
Bradley→362
Motzkin→363
Straus→363
Mikusi\'nski→363
Gosper→363
Stern--Peirce tree→363
Shallit→363
Liouville→363
transcendental→363
Kempner,→363
Lagrange→363
Matula→363
slash arithmetic→363f
rounding→363
Factorization: Discovering factors. Of integers,→364f
prime→364
Legendre→366
de la Vall\'ee Poussin→366
Vall\'ee Poussin→366
prime number theorem→366f
primes, distribution of→366f
Walfisz,→366
Weyl→366
exponential sums→366
Riemann→366f
Littlewood→366
Hardy→366
zeta function→366
Riemann hypothesis→366
Brent→367
Lehmer→367
Dickman→367
Ramaswami→367
Norton,→367
normal distribution→368
Hardy→369
Wright,→369
Erd\H os→369
Kac,→369
permutations→369
Knuth→369
Trabb Pardo→369
Monte Carlo, method for factoring→369f
Rho method, see Monte Carlo method for factoring→369f
Pollard→369
random mapping→369
Brent→371
Fermat→371f
Dickson→371
Lehman→371
perfect square→372
sieve procedure→373f
Boolean operations→373
logical operations→373
{\:tMIX}→373
AND→373
Wunderlich→374
Lehmer→374
Lehmer, Emma→374
prime numbers, verifying primality→374f
Lucas→375
Lehmer→375
Fermat's theorem→375
Fermat→375
Mersenne→375
order of $x$ modulo $n$→375
Aurifeuille→376
Dickson→376
quadratic reciprocity→377
Brillhart→378
Selfridge→378
Brillhart→378
Lehmer,→378
Selfridge→378
Wunderlich,→378
cyclotomic polynomial→378
Williams→378
Judd,→378
probabilistic algorithms→379f
random numbers, using, see also probabilistic algorithms→379f
Miller→379f
Generalized Riemann Hypothesis→380
Riemann hypothesis, generalized→380
GRH→380
ERH, see GRH→380
Weinberger,→380
Solovay→380
Strassen,→380
Rabin,→380
Traub→380
Adleman→380
algebraic integers→380
Rumely→380
continued fractions→380f
Legendre→380
Kraitchik,→380
Lehmer→380
Powers→380
Brillhart→380
Morrison→380
IBM 360/91 computer→380
Schroeppel→383f
Wunderlich→383f
Morrison,→384
Brillhart,→384
Hickerson,→384
Shanks,→384f
quadratic forms→385
Pollard→385
convolution→385
Guy,→385
Conway→385
Dixon→385
probabilistic algorithm→385f
binomial distribution→385
cryptanalysis→386f
secure communications→386f
Rivest→386
Shamir→386
Adleman→386
RSA box→386f
Random numbers, machines for generating→387
cube roots→387f
logarithmic law of leading digits→387
Lehman→388
Diffie→388
public key cryptography→388
Hellman→388
signatures, digital→388f
Rabin→389
square root modulo m→389
Mersenne→389f
perfect numbers→389
primes, useful→390
Fermat,→391
Descartes,→391
Euler→391
Lucas→391f
Pervushin→391
Powers→391
Kraitchik→391
Mersenne primes→391f
Tuckerman→391
Nickel→391
Noll→391
Slowinski→391
CRAY-I→391
Lehmer→391
linear recurrences→392f
rank of apparition→393
quadratic reciprocity→394
Fermat→394
sieve→394
Eratosthenes→394
Selfridge→395
Dixon→395
Lucas→395
Lehmer→395
Mersenne primes→395
Pratt→395
ART ON REPRO REQUIRED→395
MIX (actually 1009)→395
Pollard→396
Guy→396
Rabin→396
Jacobi symbol→396
Solovay→396
Strassen→396
L. Monier→396
Adleman→396
Riemann→396
zeta function→396
Robinson→397
Lucas→397
Lehmer→397
Dixon→397
Schnorr→397
Dixon→397
Weinberger→397
Williams→397
Jacobi symbol→397
Rabin→397
SQRT box→397
square root→398
quadratic irrationality→398
periodic continued fraction→398
continued fraction→398
palindrome→398
Shamir→398
automata→398
GAUSS→398
polynomials→399f
co\-effi\-cients→399
commutative ring with identity→399
ring→399
associative→399
commutative→399
distributes→399
degree→399
leading co\-effi\-cient→399
monic polynomial→399
multivariate polynomial→400
polynomial arithmetic modulo $m$→400
carrying→400
multiple-precision arithmetic→400
Brown,→401
Hyde,→401
Tague,→401
Collins→401
Hamblin,→401
Karatsuba→401
field→401
commutative ring with identity→401
rational numbers→401
fractions→401
complex numbers→401
real numbers→401
rational functions→401
quotient polynomial→402
remainder polynomial→402
synthetic division→402
mod→402
unique factorization domain→403f
unit→403
primes→403
reciprocal,→403
field→403
irreducible polynomial→403
multivariate polynomials→403
multiple→403
divisor→403
relatively prime→404
primitive→404
primitive polynomials modulo $p$→404
Gauss→404
Gauss, lemma about polynomials→404
content→405
primitive part→405
greatest common divisor→405
Euclid's algorithm for polynomials→405f
Stevin→405
Girard,→405
pseudo-division of polynomials→407f
commutative ring with identity→407
Euclid's algorithm, generalized→407f
rational arithmetic→409
subresultant algorithm→410f
Collins→410
Brown→410
Traub→410
Hadamard→414
resultant→415
Sylvester's determinant→415
van der Waerden→415
Blum→415
Sturm→416
roots of a polynomial→416
polynomial, roots of→416
determinant→416
Bareiss,→416
reverse of a polynomial→416
extended Euclid's algorithm→417f
analysis of algorithms→417
binary gcd algorithm→417
units→417
irreducible→417
primitive polynomials→417
Sylvester's matrix→417
Hadamard→418
Cohn→418
string polynomials→418
degree→418
noncommutative multiplication→418f
multivariate polynomials→418
free associative algebra→418
homogeneous polynomial→418
greatest common right divisor→419
least common left multiple→419
matrices, greatest common right divisor→419
accuracy of floating point→420
Sturm→420
Brown→420
rational function approximation→420
approximation, by rational functions→420
Euclid's algorithm→420
convergents→420
continued fraction→420
continuant→420
Berlekamp→420
derivative→421
Fermat→421
shift register→424
null space→425
matrix, determination of rank→425
rank of a matrix→425
reciprocal→427
Zassenhaus→428
Berlekamp→429
Moenck,→429
Distinct-degree factorization→429f
Golomb→430
Welch→430
Hales→430
Schwarz→430
Rabin→430
Cantor→430
Zassenhaus→430
factoring polynomials over the integers→431f
Newton→431
von Schubert→431
Cantor,→431
Kronecker→431
Vaughan,→433
cyclotomic polynomials→433
Hensel→433
reverse polynomial→434
logical ``and''→434
Musser,→434
Collins,→434
modular method for polynomial gcd→434f
greatest common divisors of polynomials→434f
Brown→435
Collins,→435
Moses→435f
Yun→435f
multivariate polynomials→436
Wang,→436
Musser→436
squarefree→436f
Berlekamp→436f
Chinese remainder theorem, for polynomials (exercise 3)→437
irreducible polynomials→437f
Mobius function→437
Lagrange→437
reciprocals→437
primitive root→437
Zassenhaus.→437
square root modulo $p$→437
primitive root→438
finite field→438
Galois field, see finite field→438
Eisenstein→438
multivariate polynomials→438
Hensel's Lemma→439
rational numbers→439
logical operations→439
distinct-degree factorization→439
proper factor→439
probabilistic algorithm→439
Cyclotomic polynomials→440
Mobius function→440
Squarefree factorization→440f
modular method→440
Yun→440
Collins→441
permutation→441
Pratt→441
evaluation of powers→441f
exponentiation→441f
powers, evaluation of→441f
binary number system→441
Pingala→441
Datta→441
Singh,→441
al-Uql\A \i dis\A \i →441
Saidan→441
al-B\A \i r\A un\A \i →441
Sachau→441
hardware→442
al-Kash\A \i →443
Egyptian→443
doubling,→443
halving,→443
Russian peasant method→443
Fateman,→443
factor method→443
power tree→444
Addition chains→444f
complexity of calculation→444f
optimum methods of computation, see complexity→444f
power tree→445
Dellac→445
de Jonqui\`eres→445
factor method→445
doubling→447
star step→447
small step→447
star chain→447
Fibonacci sequence→448
de Jonqui\`eres→449
Gioia,→449
Subbarao,→449
Sugunamma→449
carries→450
Thurber→451
Sch\"onhage→451
Brauer,→451
Erd\H os→451
Pr→453
Star chains→453f
Hansen→453f
multiset→454
Goulard,→458
de Jonqui\`eres→458
Thurber→458f
Hebb→458
Thurber→459
Scholz→459f
Brauer→459f
directed graph→460f
ART ON REPRO REQUIRED→460
ART ON REPRO REQUIRED→461
source→461
sink→461
topologically sort→461
equivalent addition chains→461
ART ON REPRO REQUIRED→462
dual→462
SRB→462
JAE→462
octal→462
factor method→463
oriented binary tree→463
multiset→464f
prime factorization→464
fundamental theorem of arithmetic→464
gcd→464
lcm→464
Hansen→464f
Brauer→464
binary number system→464
square-root→464
Fibonacci number→464
Straus→465
monomial→465f
Sch\"onhage→465
addition-subtraction chain→465
Lehmer→465
Yao→465
Graham→465
Yao, Frances→465
dual→466
equivalent→466
Olivos→466f
factor method→466
Downey→466
Leong→466
Sethi→466
graph→466
vertex cover→466
Miller,→466
stability→467
Horner's rule→467f
Horner→467
Coolidge,→467
Newton→467
Whiteside,→467
complex number→467f
Fourier series→467f
Goertzel,→468
division of polynomials→468
parallel computations→469f
Estrin→469
Dorn→469
radix conversion→470f
Taylor→470
derivatives→470f
Horner→470
Shaw→470
Traub→470
stability→470
Adaptation of co\-effi\-cients→471f
sine→471
cosine→471
exponential function→471
precondition→471
Pan,→471
Motzkin→471
stability→471
Fike→472
register→472
Knuth,→472
Pan→473
Eve→474
Polynomial chains→475f
Ostrowski→475
von Mises→475
Motzkin→475
chain step→475
parameter step→475
result set→475
degrees of freedom→476f
Motzkin,→476
Belaga,→477
Strassen→478
Lipton→478
Schnorr,→478
Van de Wiele→478
Motzkin→478
Pan,→478
Borodin→479
Kohavi→479
Paz→479
Horner's rule→479
rational functions→479
continued fractions, with polynomials→479
Shaw→479
Traub→479
multivariate polynomials→479f
determinant→479f
modular arithmetic→480
division mod $p$→480
Hadamard's inequality→480
characteristic polynomial→480
Wilkinson,→480
permanent→480
Valiant→480
Turing machine→480
matrix multiplication→481f
inner product→481
Winograd→481
Strassen→481
Winograd→481
determinants→482
matrix inverses→482f
Bunch→482
Hopcroft,→482
Pan→482
Bini→482
Capovani→482
Lotti→482
Romani→482
Sch\"onhage→482
Pan→482
Winograd→482
Coppersmith→482
Brent→482
complex arithmetic→482
discrete Fourier transform→482f
Yates→483
Walsh transform→483
Walsh→483
Harmuth→483
Fast Fourier Transform→483f
parallel computation→484
Lagrange→484
interpolation→484f
Newton→485
Horner's rule→485
divided differences→485
Shamir→486
secret keys→486
cryptanalysis→486
Chinese remainder algorithm→486
Newton→486
mixed-radix representation→486
fast Fourier transforms→486
Horowitz,→486
Moenck→486
Borodin→486
Traub→486
Thiele→487
reciprocal differences→487
Milne-Thompson→487
Floyd,→487
Bilinear forms→487f
tensor→487f
multiplication of complex numbers→487
complex numbers→487
Matrix multiplication→487f
Fourier transforms→487
Normal evaluation scheme→487
rank of a tensor→488f
Hitchcock→488
Strassen,→488
Winograd→488
matrix multiplication→488f
transpose→488
Pan→488
Hopcroft→489
Musinski,→489
realization of a tensor→489
polynomials, multiplication of→489f
multiplication of polynomials→489f
Winograd→490f
Chinese remainder theorem→491
cyclic convolution→491f
convolution→491f
cyclotomic polynomial→492
Chinese remainder→492
partial fraction expansion→492
interpolation→492
Winograd→494f
Fourier transforms→494
fast Fourier transform→494
multiplication of polynomials→494f
companion matrix→494
cyclotomic polynomials→496
Winograd→496
multivariate polynomials→496
Ja'Ja',→496
Borodin→496
Munro→496
Horner's rule→496
de Jong→497
van Leeuwen→497
Shaw→497
Traub→497
factorial power→497
Ryser→497
permanent→497f
Fast Fourier transforms→497
FFT→497
divided difference→498
Newton→498
interpolation→498
adapted co\-effi\-cients→498f
FADD→498
FMUL→498
Pan→498
Eve→499
polynomial chain→499f
Horner's rule→499
degrees of freedom→499f
multivariate polynomials→499
van der Waerden→499
Blum→499
Motzkin→500f
rational functions→500
Pan→501
Horner's rule→501
complex numbers, multiplication of→501
Paterson→501
Stockmeyer→501
tensor→501f
rank→501f
bilinear forms→502f
Tarski→502
direct sum→502f
direct product→502f
Winograd→502f
matrix multiplication→502f
cyclic convolution→502f
Fourier transform→502
discrete Fourier transform→502
Strassen→503
quadratic forms→503
Nussbaumer→503
negacyclic convolution→503
Pan→503
trilinear representation→503
border rank→505
Pan→505
Winograd→505
power series→506f
asymptotic expansions→506
addition of power series→506
multiplication of power series→506
Cauchy→506
division of power series→506
on-line algorithm→506f
fractions→507
exponentiation of power series→507
square root→507
Miller→507
Henrici→507
differentiation→507
reversion of series→508f
Lagrange→508
Thacher→510
Brent→510
Kung→510
Newton's method→510
semi-on-line→510
Bramhall→511
Chapple→511
Iteration of series→511f
Schr\"oder function→512f
Schr\"oder→512
Brent→512f
Traub→512f
division of power series→514
Kung→514
Lagrange's inversion formula→514
Composition of power series→514
polynomial division→515
Rational function approximation→515
Pad\'e→515
extended Euclidean algorithm→515
Brent→515
Traub→515
Jeremiah→515
PEIRCE,→516
LeVeque,→516
Poisson distribution→517
semigroup→517
idempotent→517
Gosper→518
Sedgewick→518
Szymanski→518
Jansson,→518
Rapoport,→519
Harris,→519
Sobol',→519
Purdom→519
Williams,→519
Kruskal,→520
Riordan,→520
Marsaglia→521
Bray→521
Euler's theorem→523
MacLaren→525
Marsaglia,→525
Greenberger,→525
RANDU→525
Mantel,→526
Coveyou→527
Wall,→527
Jansson→527
Ward→528
Robinson,→528
Waterman→529
Dewey decimal notation→530
Lempel→530
Brent→530
Doob→532
Donsker→532
independent→532
generating function→535
Bofinger→535
Bofinger→535
``inclusion-exclusion'' principle→536
Lagrange's identity: $whatever$→536
Franklin→542
Gauss→543
Minkowski→544
Fermat,→544
Euclid's algorithm→544
Gaussian integers→544
Grube,→547
Euler phi function→548
Zaremba→548
Cusick→548
Borosh→548
Niederreiter→548
MacLaren→549
geometric distribution→549
bin-packing \send 0{NP complete problem→550}\ifhmode {\!}\else {} problem→550
NP complete problem→550
positive semidefinite→551
convolution→551
L\'eger→552
Marsaglia→552
continuous Poisson distribution→552
continuous binomial distribution→553
Ahrens→553
Dieter→553
Tocher,→553
Walker→555
alias→555
Wong→555
Easton→555
complete binary tree→555
Stanley→558
Herzog→558
Ville→560
Turing→561
Knuth→561
Reeds→561
number sentences→562
Mandelbrot→564
twindragon→564
dragon curve→564
Davis→564
Knuth,→564
Graham→565
Odlyzko→565
dragon curve→566
MacMahon,→566
Sands,→567
inclusion and exclusion→567
Fibonacci number→568
Yohe,→569
Wynn,→570
Friedland,→570
Morris,→570
interval arithmetic→570
Kahan→571
Chan→572
Lewis→572
Hanson,→573
Bohlender→573
normalization→573
Veltkamp→573
Hansen,→574
Kahan.→574
cancellation errors, avoiding→574
Operands: Quantities that are operated on; e.g., $u$ and $v$ in the calculation of $u+v$→575
dilogarithm→578
Landau→578
Diaconis→578
Cohen,→579
Brent,→584
Fraenkel,→585
balanced mixed-radix→586
10-adic→587
chirp transform (exercise 8)→588
evaluation of polynomials (exercise 8)→588
Bluestein→588
inverse transforms→588
Steele Jr.→589
White→589
nonary→591
Sch\"onhage→592
Weyl's→592
Keir,→592
extended arithmetic→593
hexadecimal→593
inclusion and exclusion→593
Mertens→595
least common multiple→595
Collins→595
brute force→596
summation by parts→597
factorial powers→597
Brent→597
Smith→598
Dickson→598
Sch\"onhage→598
Penk→599
reciprocal modulo $m$→599
Mend\`es France→602
Tur\'an→602
Gosper→602
addition of continued fractions→602
Euler→602
Davis→603
continuants→604
Khinchin→604
M\"obius's inversion formula→604
Kronecker→605
de Bruijn→605
Zaring→605
Rieger→605
Dupr\'e→605
Binet→605
Bachmann→605
Hardy→606
Wright→606
comparison of continued fractions→606
Stern→607
Peirce→607
Lehmer→607
continuant→607
dragon sequence→607
dragon curve→607
Stern--Peirce tree→608
Waterman→608
Pollard→608
Brent→608
Carmichael numbers→609
Fibonacci sequence→611
Golomb's constant→611
Billingsley→611
Galambos→611
Knuth→611
Trabb Pardo→611
MIX (actually 1009)→612
Lehmer, D. N.→612
Carmichael number→613
R\=am\=anujan→613
Monier→613
von Mangoldt→613
logarithmic integral→614
quadratic reciprocity→614
multiplication modulo m→614
Proth→614
Robinson→614
Plass→614
de Bruijn→614
Halberstam→614
combinations with repetitions→614
random numbers, using→615
prime→615
prime number theorem→615
Robinson, Julia→616
Fibonacci numbers→616
logical→617
AND→617
Cook→617
reverse→618
resultant→619
discriminant→619
Loos→619
Schwartz→619
Sturm→619
Schmidt's orthogonalization process→620
Bergman→620
Cohn,→620
continuant polynomials→621
Cahen,→621
Triangularization→621
matrix triangularization→621
Collins,→622
Tobey,→622
Heindel,→622
Kronecker→623
inclusion and exclusion→623
Stirling numbers→624
Swinnerton-Dyer→625
Frobenius→625
Galois group→625
null space→625
Berlekamp→625
Zassenhaus→625
Shanks→626
Tonelli,→626
Gauss's lemma→626
Vicente Gon\c calves→627
Mignotte,→627
Payafar→627
Gel'fond→627
Zassenhaus→628
Hensel→628
$p$-adic numbers→628
Yun,→628
discriminant→628
logical ``or''→629
Brown,→629
Lehmer,→629
de Bruijn→629
trie→630
probabilistic algorithm→630
Gauss→631
Kronecker,→631
Yun→631
Wang→631
Trager→631
Yun→631
recursive→632
distinct-degree factorization→632
Frobenius→632f
Galois group→632f
van\penalty 999\ der\penalty 999\ Waerden→632
Chebotarev→632
Weinberger→632
permutation→632
generalized Riemann hypothesis→632
GRH→632
zeta function→632
algebraic number field→632
discriminant→632
Commutative law→636
Associative law→636
Distributive laws→636
Idempotent→636
Absorption laws→636
Counting law→636
partial ordering→636
context-free grammar→636
multiset→636
bag→636
de Bruijn→636
generating function→636
Dirichlet→637
hardware→637
linear recurrence→637
Miller→637
Brown→637
logical ``or''→637
Sch\"onhage→638f
Erd\H os→638
negative digits→638
Newman→638
quadratic residues→638
Dobkin→638
Lipton→638
commutativity→639
binary trees→639
Catalan numbers→639
dual→639
Papadimitriou→639
monomial→639
Pippenger→639
NP complete→639
Newton→640
homogeneous polynomial→640
Gray code→640
Jurkat→641
Ryser→641
matrix multiplication→641f
Hopcroft→641
Kerr→641
Probert→641
Laderman→641
S\'ykora,→641
Lafon→641
Winograd→641
Pan→641
interpolating→641
Runge→642
K\"onig→642
Cooley→642
Tukey,→642
Lewis,→642
Welch,→642
Singleton,→642
Pease,→642
Berglund,→642
Macnaghten→642
Hoare,→642
Vari→642
Pan,→644
arithmetic chains→646
Winograd,→646f
Revah→647
Pan→647
Ungar→647
Munro→647
Buneman→647
Alt→647
van Leeuwen→647
division of complex numbers→647
Savage,→648
Borodin→648
Cook→648
Rivest→648
Van de Wiele→648
de Groote→648
Strassen→648
Howell→648
fast Fourier transform→651
Nussbaumer→651
convolutions, multidimensional→651
Quandalle→651
Pollard,→652
primes, useful→652
Robinson,→652
Golomb→652
Brockett→652
Dobkin→652
Brown→652
polynomial multiplication→652
recursive→652
fast Fourier transform→653
analysis of algorithms→654
Yates→654
Fletcher→654
Silver→654
Winograd→654
Bini→654
Pan→654
Pan→655
Bini→655
Sch\"onhage→655
Brent→656
Newton's method→656
Traub→656
Sieveking,→656
composition→656
on-line algorithm→657
Brent→657
Kung→657
reverse of a polynomial→657
polynomial remainder sequence→657
Toeplitz→657
interpolation→657
Gustavson→657
Yun→657
multiple-precision, table of constants→659f
OCTAL→660
Wrench→661
Peters→661
Abramowitz→661
Stegun→661
Knuth→661
Buckholtz→661
harmonic numbers→661f
Bernoulli numbers→661
Fibonacci numbers→661
Kronecker→663